package com.atwy.tree;

import java.util.*;

/**
 * 哈夫曼树
 */
public class HuffmanTreeDemo {
    public static void main(String[] args) {
        // 创建哈夫曼树的案例
        /*int[] array = {13, 7, 8, 3, 29, 6, 1};
        HuffmanTree huffmanTree = new HuffmanTree(array);
        huffmanTree.preOrder();*/

        // 哈夫曼编码的案例
        String msg = "i like you hello world  do you like";
        HuffmanTree tree = new HuffmanTree(msg);

        Map<String, String> huffmanMap = tree.getHuffmanMap();

        System.out.println(huffmanMap);

        String huffmanCode = tree.getHuffmanCode();
        System.out.println(huffmanCode);

        System.out.println(Arrays.toString(tree.getArray()));
        System.out.println(Arrays.toString(tree.getCs()));
    }

}


class HuffmanTree {
    Node root;
    private int[] array;
    private String[] cs;
    private Node[] nodes;// 存放原始数组对应的结点，为后续得到哈夫曼编码提供功能

    private Map<String,String> huffmanMap = new HashMap<>();// 哈夫曼编码表，以字符为key，哈夫曼编码为value存放数据

    private String msg2HuffmanCode;

    public HuffmanTree(int[] array) {
        this.array = array;
        createHuffmanTree(array);
        encode(root, "");// 从哈夫曼树的根开始编码，根默认编码是空字符串
    }

    public HuffmanTree(String msg){
        // 统计msg中各字符的个数
        Map<String,Integer> map = new HashMap();
        for (int i = 0; i < msg.length(); i++) {
            String letter = String.valueOf(msg.charAt(i));
            if(map.containsKey(letter)){
                map.put(letter,map.get(letter)+1);
            }else {
                map.put(letter,1);
            }
        }

        // 将msg中字符的个数按照字符
        int mapSize = map.size();
        this.array = new int[mapSize];
        this.cs = new String[mapSize];
        int k = 0;
        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<String, Integer> next = iterator.next();
            cs[k] = next.getKey();
            array[k] = next.getValue();
            k++;
        }

        createHuffmanTree(array);

        encode(root,"");

        for (int i = 0; i < mapSize; i++) {
            huffmanMap.put(cs[i],convertHuffmanCode(i));
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < msg.length(); i++) {
            sb.append("#").append(huffmanMap.get(String.valueOf(msg.charAt(i))));
        }

        msg2HuffmanCode = sb.substring(1);

    }

    public Map<String, String> getHuffmanMap() {
        return huffmanMap;
    }

    public String getHuffmanCode(){
        return msg2HuffmanCode;
    }

    public int[] getArray() {
        return array;
    }

    public String[] getCs() {
        return cs;
    }

    /**
     * 创建哈夫曼树
     *
     * @param array
     */
    private void createHuffmanTree(int[] array) {

        nodes = new Node[array.length];
        // 这里借用集合的排序
        List<Node> nodeList = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            nodes[i] = new Node(array[i]);
            nodeList.add(nodes[i]);
        }

        while (nodeList.size() > 1) {

            // 排序
            Collections.sort(nodeList);

            // 取出最小权值的两个结点
            Node node1 = nodeList.get(0);
            Node node2 = nodeList.get(1);
            // 权值相加构成 父结点
            Node parent = new Node(node1.value + node2.value);
            parent.left = node1;
            parent.right = node2;

            // 移除最小的两个结点
            nodeList.remove(node1);
            nodeList.remove(node2);
            // 把组成父结点加入列表中
            nodeList.add(parent);

        }
        // 最后列表中只有一个结点就是根结点
        this.root = nodeList.get(0);

    }

    /**
     * 对每个结点进行编码，左结点补0，右结点补1
     */
    public void encode(Node node, String code) {
        if (node == null) {
            return;
        }
        node.code = code;
        encode(node.left, node.code + "0");
        encode(node.right, node.code + "1");
    }

    /**
     * 输入下标得到对应的哈夫曼编码
     *
     * @param index
     * @return
     */
    public String convertHuffmanCode(int index) {
        return nodes[index].code;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("是空树，不能遍历");
        }
    }

    public static class Node implements Comparable<Node> {
        int value;// 结点的权值
        String code;// 结点对应的二进制编码
        Node left;// 指向左子结点
        Node right;// 指向右子结点

        public Node(int value) {
            this.value = value;
        }

        /**
         * 前序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Node{");
            sb.append("value=").append(value);
            sb.append('}');
            return sb.toString();
        }

        @Override
        public int compareTo(Node other) {
            // 表示从小到大排序
            return this.value - other.value;
        }
    }


}

